package cn.zifangsky.heap.questions;

import cn.zifangsky.queue.PriorityQueue;
import org.junit.Test;

import java.util.Arrays;
import java.util.Collection;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * 求很大一个的乱序序列的前K个最小（大）的元素？求第K个最小（大）的元素？
 *
 * @author zifangsky
 * @date 2020/5/14
 * @since 1.0.0
 */
public class Problem_001_TopK {
    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        //1. 生成 1~100 的整数
        Integer[] arr = IntStream.rangeClosed(1, 100).boxed().toArray(Integer[]::new);

        //2. 将数组的顺序打乱
        shuffle(arr);

        //3. 求前10个最小的元素，以及第10小的元素
        Integer[] arr1 = Arrays.copyOf(arr, arr.length);
        Solution<Integer> solution1 = new Solution<>(PriorityQueue.Mode.MAX, 10);
        solution1.addAll(Arrays.asList(arr1));

        System.out.println(Arrays.toString(solution1.toArray(new Integer[10])));
        System.out.println("数组中第10小的元素：" + solution1.getKth());


        //4. 求前10个最大的元素，以及第10大的元素
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Solution<Integer> solution2 = new Solution<>(PriorityQueue.Mode.MIN, 10);
        solution2.addAll(Arrays.asList(arr2));

        System.out.println(Arrays.toString(solution2.toArray(new Integer[10])));
        System.out.println("数组中第10大的元素：" + solution2.getKth());
    }


    static class Solution<T extends Comparable<? super T>> {
        /**
         * 优先队列
         */
        private PriorityQueue<T> queue;

        /**
         * 前K个最小（大）的元素
         */
        private int k;

        public Solution(PriorityQueue.Mode mode, int k) {
            this.queue = new PriorityQueue<T>(mode, k);
            this.k = k;
        }

        /**
         * 添加一个集合进来
         */
        public void addAll(Collection<? extends T> c){
            for(T e : c){
                this.add(e);
            }
        }

        /**
         * 往队列中添加新值
         */
        public void add(T data){
            if(data == null){
                return;
            }

            //1. 如果当前优先队列中个数不足 K 个，则直接插入到队列
            if(queue.size() < k){
                queue.push(data);
                return;
            }

            //“最大优先队列”或者“最小优先队列”
            PriorityQueue.Mode mode = queue.getMode();
            //队列头节点
            T head = queue.top();

            /**
             * 以下两种情况不更改优先队列中的值
             *     最小优先队列（前K个最大的元素）：新值比队列中最小值（头结点）还小
             *     最大优先队列（前K个最小的元素）：新值比队列中最大值（头结点）还大
             */
            if(head != null && PriorityQueue.Mode.MIN.equals(mode) && data.compareTo(head) <= 0){
                return;
            }
            if(head != null && PriorityQueue.Mode.MAX.equals(mode) && data.compareTo(head) >= 0){
                return;
            }

            //2. 当触发上述两种情况之外的情况，则使用新值替换原来的头结点，成为TopN之一
            queue.pop();
            queue.push(data);
        }

        /**
         * 返回第K个最小（大）的元素
         */
        public T getKth(){
            return queue.isEmpty() ? null : queue.top();
        }

        public T[] toArray(T[] a){
            return queue.toArray(a);
        }
    }

    /**
     * 洗牌
     */
    private void shuffle(Integer[] arr){
        if(arr == null || arr.length < 1){
            return;
        }
        Random rnd = new Random();

        for(int i = (arr.length -1); i > 0; i--){
            swap(arr, i, rnd.nextInt(i));
        }
    }

    private void swap(Integer[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
